1. Field of the Invention
The present invention generally relates to the distribution of buffer space between multiple sources. More particularly, the invention relates to a fair and efficient method of controlling allocation of a shared buffer pool.
2. Background of the Invention
In computer systems and networks, buffers are a convenient means of storing commands, requests, and data that are in transit from one location to another. Buffers may be used in a variety of applications. They may be used in network switching devices to temporarily hold data packets while networks congestion subsides or while the switch determines the location to which the data must be forwarded. It is not uncommon for network switches to manage traffic for a plurality of sources. Buffers may also be used in memory and data allocation. An example of the latter would be a data read/write request buffer that must allocate requests from multiple sources. A common problem in systems using a shared buffer space is signal traffic that creates congestion and may lead to buffer overflow and monopolization by one or more of the buffer sources.
Ideally, a system comprising a buffer with multiple sources should accomplish several tasks. First, the system should not deliver data, commands, or requests to the buffer if the buffer does not have any free space. This prevents data loss or packet drops which may require that the data packet be re-sent resulting in even greater bandwidth loss than simply holding the data until buffer space becomes available. Secondly, access to buffer space by the multiple sources should preferably be allocated in a fair manner. The sources should have fair access to the buffer so a source does not become backlogged while other sources are able to deliver data freely. This does not necessarily imply that the allocation needs to be equal for each source. For instance, one source may be given priority over the others. However, even in this scenario, it is important to prevent complete monopolization by the source that has priority.
One conventional solution to the problem of fair allocation of a shared buffer space is hard partitioning of the buffer space. For example, if a buffer has 16 data spaces and the buffer is shared among 4 sources, each source may be allocated four buffer slots. This method of allocation is certainly fair but may be horribly inefficient. If one of the sources has a string of data that ideally could be burst to the buffer, congestion may occur because the source only has four buffer spaces available. The remaining 12 buffers could be used to hold the burst of data, but instead may lie dormant because of the hard partitioning.
If prior knowledge exists about the type of traffic that can be expected from the sources, the hard partitioning may be altered to allocate more buffer space to one source or another. For instance, in the example given above, seven buffer spaces may be allocated to one source while the other three sources are allocated three spaces each. This allocation may alleviate congestion for the prioritized source, but does not prevent the burst congestion for of the other sources. In either case, hard partitioning tends to preclude use of at least a fixed percentage of the buffer space unless all sources are continuously accessing the buffer.
Another conventional solution to the problem of fairly and efficiently allocating buffer space is with stop and go commands issued by the buffer. In this type of system, the buffer is configured to keep track of available spaces within the buffer. During normal operation with light traffic, each source receives a “go” signal from the buffer indicating that buffer space is available. As buffer space becomes limited, the buffer may send “stop” signals to the individual sources to halt data transmission to the buffer. This approach offers better use of the buffer space because the sources are not limited to a fixed percentage of the buffer space. However, some risk is involved in this type of embodiment because a finite time exists between the moment the buffer sends out a stop command and the moment the source receives and responds to the stop command. During this finite time, it is possible for additional data to be transmitted to the buffer from the various sources. If the buffer was sufficiently close to being full and enough data was sent to the buffer before the stop commands were received by the sources, buffer overflow may occur and data may be lost. To prevent this, stop commands are usually sent well in advance of the buffer filling to capacity. Thus, if all buffer sources are bursting data to the buffer, the stop command is preferably timed so that the sources stop sending data to the buffer before the buffer capacity is filled. Unfortunately, the side effect of sending the stop commands early is that the maximum capacity of the buffer will not be used when the buffer sources are not simultaneously sending bursts of data. The stop/go command solution to this buffer allocation problem is an improvement over the hard partitioning solution, but presents problems of either overflow or inefficient use of the whole buffer.
It is desirable therefore to develop a fair and efficient means of allocating buffer space among several sources. The allocation preferably prevents monopolization by any of the buffer sources. The allocation method also preferably takes advantage of the full capacity of the buffer space without the possibility of buffer overflow. The system may advantageously be applied to a plurality of buffer sources and may also be applied to a variety of applications.